1. Field of the Invention
This invention relates to map display systems and methodologies. More particularly, this invention relates to the near optimum placement of cartographic labels.
2. Description of the Related Art
Map labeling involves determining a near optimal placement of labels that identify various cartographic features. Typically when drawing a map, there are requirements to label points such as cities, lines such as rivers or political borders, and real features such as swamps, parks or forests. The art of cartography has a long history, and label placement, being part of this art, does not fall short. For many centuries, cartographers have devised some general rules that a well-formed label placement must follow. Labels must be positioned such that they are legible and follow aesthetic quality criteria. A label must be placed in the best position among all legible positions. Labels should, in spite of their incorporation into densely crowded graphics of the map, be easily read, easily discriminated from other labels, and quickly located. The label must permit associativity. That is, the label and the object to which it belongs should be easily associated. A principle of noninterference must be observed. Labels should disturb other map contents as little as possible. Finally, labels should assist the reader to identify spatial situations, territorial extent, connections, importance, and to differentiate objects.
While there are many possible ways to label map features and to resolve conflicts, a well-formed labeling should result in a legible and attractive map that provides easy access to its information. Optimizing label placement in general is a difficult problem for which closed form solutions are either impractical or simply not available.
In map production, the problems of placing labels of a set of nodes or points are referred to as the “node label placement problem” (NLP), and the “point feature label placement problem”, respectively. The problem of placing labels of lines or edges is referred to as the “edge label placement problem” (ELP). A related problem is the placement of area labels or face labels. All three problems are NP-hard. Therefore, algorithms based on exhaustive search are impractical due to exponential explosion, even when attempting to solve the problems independently. These three problems are referred to collectively as the “graphical feature label placement problem” (GFLP).
While the particular heuristics that have been used to resolve label conflicts vary, all depend upon three important assumptions: (1) Each individual label can be placed in one of a relatively small number of positions near or on the feature it annotates. The search for a new label position may be an iterative process, but only a few positions for each label are typically evaluated by most label placement algorithms. (2) The relative quality of individual label positions can be measured. (3) Each label should be placed relative to its feature in the best possible position that avoids overlapping with other labels or map symbols. Essentially, the GFLP is a combinatorial optimization problem.
Approaches that have been proposed to solve the map labeling problems are based on greedy algorithms, algorithms that simulate physical models, and algorithms that reduce the labeling problem to a variant of zero-one integer programming, such as relaxation methods, e.g., Lagrangian relaxation methods.
Using physical relaxation methods, labels are moved smoothly in response to virtual forces generated by label-label and label-symbol overlaps, while remaining tethered to the symbols they tag.
Using zero-one integer programming, scores associated with each label's candidate positions are refined iteratively to better reflect the merit of different label positions.
In gradient descent methods, a randomly generated labeling is improved monotonically by considering all alternative positions for each label, chosen from a discrete set, and making the single label move in a manner that most improves the global quality of the map labeling.
Genetic algorithms have also been applied to map labeling optimization. Genetic algorithms are iterative techniques, based on the paradigm of Darwinian evolution, and changes between iterations are not restricted to gradient descent but rather include a degree of randomness. Techniques based on genetic algorithms require careful tuning, as they are prone to converge on local optima.
Simulated annealing is another variant of the gradient descent technique, in which single label moves that worsen the quality of the labeling are performed occasionally in order to avoid becoming entrapped by local optima.
Formerly, map labels could be optimized more or less at leisure, using off-line approaches. However, systems for providing drivers with in-vehicle electronic routing maps and navigation aids have emerged. These systems are commonly coupled to a location-finding device in the vehicle, such as a Global Positioning System (GPS) receiver. The GPS receiver automatically determines the current location of the vehicle, to be displayed on the map and used in determining routing instructions. In-vehicle navigation systems fall into two general categories: “on-board” systems, in which the map data are stored electronically in the vehicle (typically on optical or magnetic media); and “off-board” systems, in which the map data are furnished by a remote map server. These systems typically use a client program running on a smart cellular telephone or personal digital assistant (PDA) in the vehicle to retrieve information from the server over a wireless link, and to display maps and provide navigation instructions to the driver. The off-board systems are particularly versatile, but may require the dynamic production of maps responsively to changing location information transmitted by the vehicle to the remote map server. This can place a significant computational burden on the remote map server.
The above-noted methods reflect progress in solving each component of the graphical feature label placement problem individually, but there is as yet no suitable integrated method that solves both of the graphical feature label placement problems simultaneously and in reasonable time so as to satisfy modern requirements.